1. Field of the Invention
This invention relates generally to arbitrating access to a shared device, and in particular to arbitration methods and arbitration units which provide a higher access rate for critical devices in systems without increasing maximum latency for other devices.
2. Description of the Related Art
In complex systems, many devices may access a shared device. For example, in an IBM PC compatible computer system many devices, such as a modem, a sound card, a video card, and a SCSI card, may share a single ISA bus. Similarly, various devices of a system may share a common memory device. In systems with a shared device, an arbitration unit is commonly used to control access to the shared device.
FIG. 1 depicts a sample system having a shared device 120. Devices 101-109 are coupled to and share shared device 120. An arbitration unit 100 controls which of devices 101-109 can access shared device 120. Each of devices 101-109 has a request output terminal R and a grant input terminal G coupled to arbitration unit 100. Arbitration unit 100 has a corresponding request input terminal Rx and grant output terminal Gx for device x, where x is an integer representing any one of devices 101 to 109. Specifically, request output terminal R of device 101 is coupled to request input terminal R101 of arbitration unit 100. Similarly, grant input terminal G of device 101 is coupled to grant output terminal G101 of arbitration unit 100. Although the system of FIG. 1 uses nine devices, those skilled in the art will appreciate that a fixed number of devices is used for example only and that the concepts and systems shown can be easily adapted to any number of devices. Furthermore, in some systems a single physical device is treated as multiple devices in the arbitration scheme, e.g., if the single physical device can make requests of different priority and access time. Moreover, the arbitration methods described herein can be used to arbitrate software objects. For example, in a multitasking computer system, different application programs may need to access a shared resource.
When a device, for example device 101, desires to access shared device 120, device 101 drives an active state (e.g., logic high) on request output terminal R of device 101. If arbitration unit 100 decides to grant device 101 access to shared device 120, arbitration unit 100 drives an active state on grant output terminal G101, which is connected to grant input terminal G on device 101. When device 101 detects the active state on grant input terminal G of device 101, device 101 accesses shared device 120. Typically, device 101 retains access to shared device 120 until device 101 indicates that device 101 no longer requires access to shared device 120. The time between receiving a grant to access shared device 120 and relinquishing shared device 120, is called the access time. A common method for relinquishing shared device 120 is for device 101 to maintain an active state on request output terminal R until device 101 no longer requires access to shared device 120.
Arbitration unit 100 can use a variety of arbitration schemes. For example a simple arbitration scheme is to grant access to shared device 120 to the first device making a request. Since multiple devices may request access to shared device 120 simultaneously, the requests are queued so that the device with the oldest pending request is granted access to shared device 120. For example, if device 101 is using shared device 120 and device 104 asserts a request followed later by a request from device 102, arbitration unit 100 would grant device 104 access to shared device 120 after device 101 relinquishes shared device 120. After device 104 relinquishes shared device 120, arbitration unit 100 grants device 102 access to shared device 120.
Since this scheme guarantees all devices equal access to shared device 120, the latency, i.e., the time between making a request to access shared device 120 and completing the requested access to shared device 120, can be quite high. The access time, i.e., the time between receiving a grant to access shared device 120 and relinquishing shared device 120, of each device 101 through 109 varies. Therefore each device is typically limited to access shared device 120 for at most a maximum access time, i.e., the maximum time a device may retain access to shared device 120. In some systems, the maximum access time of each device is unique to that device. In such systems, the maximum latency of accessing shared device 120, i.e., an upper bound for the time between making a request to access shared device 120 and completing the requested access to shared device 120, for a particular device is the sum of the maximum access time of each device. For the simple arbitration method, the maximum latency for a particular device occurs if every other device has a pending request for shared device 120 when the particular device makes a request for shared device 120.
However, each device may have a different maximum latency requirement, i.e., an upper bound on the amount of latency a device can tolerate, for access to shared device 120. In general, high priority devices will have a lower maximum latency requirement for accessing shared device 120 and low priority devices will have a higher maximum latency requirement for accessing shared device 120. The simple arbitration scheme of granting access to shared device 120 based on the time of the request is not easily adaptable to provide different maximum latencies of accessing shared device 120 for devices 101 to 109 having different levels of priority.
FIG. 2(a) conceptually illustrates a hierarchical arbitration scheme which can provide different maximum latencies of accessing shared device 120 for different groups of devices. Devices 101-109 are divided into groups based on the maximum latency requirement of accessing shared device 120 for each device. In the example of FIG. 2(a), the devices with the highest priority, i.e., lowest maximum latency requirements, for example, device 101, device 102, and device 103 are in group 0. Devices with slightly lower priority, such as device 104, are in group 1. Group 2 contains low priority devices, such as device 105 and device 106. Finally, Group 3 is for the lowest priority devices, such as device 107, device 108, and device 109. Conceptually all of the devices in Group 3 are treated as one device in Group 2. Similarly all of the devices in Group 2 are treated as one device in Group 1 and the devices of Group 1 are treated as one device in Group 0. Each device in group X can be referred to as a group X device. For example, device 101 is a group 0 device.
When the system is powered up or reset, one device in each group begins with the highest precedence for that group. In this example, device 101, device 104, device 105, and device 107 begins with the highest precedence for group 0, group 1, group 2, and group 3, respectively. The order of precedence is assigned circularly from the device with the highest precedence in a group as illustrated by the arrows in FIG. 2(a). For example, when device 101 has the highest precedence in group 0, device 102 has the second highest precedence in group 0. Device 103 has the third highest precedence in group 0. Group 1, treated as a single group 0 device, has the fourth highest precedence in group 0. Conceptually, the devices are circularly ordered within the group as shown by the arrows in FIG. 2(a). The precedence within the group is then assigned by selecting the highest-precedence device and assigning decreasing precedence to each device of the group following the circular order of the devices within the group.
The precedence ranking within a group is reassigned after a device within the group has access to shared device 120. Specifically, if a device is granted access to shared device 120, the device with access to shared device 120 is assigned the lowest precedence in the group and is designated the lowest-precedence device within the group. Therefore, the next device in the group following the circular ordering of the group as shown by the arrows is assigned the highest precedence and is designated as the highest-precedence device in the group. The remaining devices in the group are then assigned decreasing precedence following the circular ordering of the devices in the group. For example, if device 102 has the highest precedence in group 0 but only device 103 and device 101 are requesting access to shared device 120, device 103 is granted access to shared device 120. Then group 1, treated as a single device within group 0, is assigned the highest precedence within group 0. Device 101 is assigned the second highest precedence within group 0. Device 102 is assigned the third highest precedence within group 0, and device 103 is assigned the fourth highest (i.e., the lowest) precedence in group 0. The preceding example also illustrates that even though device 102 had the highest precedence within group 0 and device 102 did not request access to shared device 120, device 102 is does not retain the highest precedence after a device is granted access to shared device 120. Precedence within group 1, group 2, and group 3 are assigned similarly.
Arbitration unit 100 (FIG. 1) grants the highest-precedence requesting device access to shared device 120. The highest-precedence requesting device is the device with the highest precedence among all devices requesting access to shared device 120. Devices within group 1 are granted access to shared device 120 only if no group 0 device with a higher precedence than group 1, treated as a single device in group 0, is requesting access to shared device 120. For example, if device 102 has the highest precedence in group 0, device 104 can be granted access to shared device 120, only if neither device 102 nor device 103 is requesting access to shared device 120. In addition, device 104 must have a higher group 1 precedence than any other device in group 1, which is also requesting access to shared device 120.
Group 2 devices are granted access to shared device 120 only if no group 0 devices having higher precedence than group 1, treated as a single device in group 0, are requesting access to shared device 120 and no group 1 devices having higher precedence than group 2, treated as a single device in group 1, are requesting access to shared device 120. Similarly, group 3 devices are granted access to shared device 120 only if no group 0 devices having higher precedence than group 1, treated as a single device in group 0, are requesting access to shared device 120; no group 1 devices having higher precedence than group 2, treated as a single device in group 1, are requesting access to shared device 120; and no group 2 devices having a higher precedence than group 3, treated as a single device in group 2, are requesting access to shared device 120. Thus each device in the arbitration scheme is assigned a unique precedence within a hierarchy of precedences.
For example, the order of precedence upon power on or reset for the arbitration scheme of FIG. 2(a) from highest precedence to lowest precedence is device 101, device 102, device 103, device 104, device 105, device 106, device 107, device 108, and device 109. This precedence order can be obtained by beginning at group 0 and expanding each group within another group. Beginning with group 0 the precedence order is device 101, device 102, device 103, and group 1. Expanding group 1 produces the precedence order as device 101, device 102, device 103, device 104, and group 2. Expanding group 2 produces the precedence order as device 101, device 102, device 103, device 104, device 105, device 106, and group 3. Finally, expanding group 3 produces the precedence order as device 101, device 102, device 103, device 104, device 105, device 106, device 107, device 108, and device 109.
If device 105 is given access to shared device 120, the precedence order becomes device 101, device 102, device 103, device 104, device 106, device 107, device 108, device 109, and device 105. Conceptually beginning at group 0, the precedence order is device 101, device 102, device 103, and group 1, since granting device 105 access to shared device 120 requires conceptually granting group 1, as a single group 0 device, access to shared device 120, which results in group 1 having the lowest precedence in group 0. Expanding group 1 produces the precedence order as device 101, device 102, device 103, device 104, and group 2; since granting device 105 access to shared device 120 requires conceptually granting group 2, as a single group 1 device, access to shared device 120, which results in group 2 having the lowest precedence in group 1. Expanding group 2 produces the precedence order as device 101, device 102, device 103, device 104, device 106, group 3, and device 105, since device 105 now has the lowest precedence in group 2. Expanding group 3 results in the precedence order as device 101, device 102, device 103, device 104, device 106, device 107, device 108, device 109, and device 105.
If device 102 is next granted access to shared device 120 then the order of precedence becomes device 103, device 104, device 106, device 107, device 108, device 109, device 105, device 101, and device 102. Conceptually beginning at group 0, the precedence order is device 103, group 1, device 101, device 102, since device 102 now has the lowest precedence in group 0. Expanding group 1 produces the precedence order as device 103, device 104, group 2, device 101, and device 102. Expanding group 2 produces the precedence order as device 103, device 104, device 106, group 3, device 105, device 101, device 102. Expanding group 3 results in the precedence order as device 103, device 104, device 106, device 107, device 108, device 109, device 105, device 101, and device 102.
The arbitration scheme illustrated by FIG. 2(a) can be used with any number of devices arranged within any number of groups. Therefore, maximum latency calculations within groups are generally approximated by groups. The specific maximum latency for any member of a group is less than the approximated maximum latency of the group. For a general case where Nx is the number of members in group x, and Amax is the maximum access time of any device, the maximum latency LGx of group x is as follows:
LG0=N0*Amax PA1 LG1=N1*LG0=N1*N0*Amax PA1 LG2=N2*LG1=N2*N1*N0*Amax, PA1 LGx=Nx*LG(x-1)=Nx*N(x-1)* . . . *N0*Amax.
and in general
The actual maximum latency of a device in group x is less than or equal to LGx.
For the specific embodiment of FIG. 2(a), the maximum latency for each device with Lxxx being the maximum latency for device xxx, Axxx being the maximum access time of device xxx, AGx being the maximum access time of any member of group x, and MAX (a,b,c)=the maximum number in the set of numbers a, b, and c, are as follows:
______________________________________ AG1 = MAX (A104, A105, A106, A107, A108, A109) AG2 = MAX (A105, A106, A107, A108, A109) AG3 = MAX (A107, A108, A109) L101 = A102 + A103 + AG1 + A101 L102 = A103 + AG1 + A101 + A102 L103 = AG1 + A101 + A102 + A103 L104 = A101 + A102 + A103 + AG2 + A101 + A102 + A103 + A104 L105 = A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + AG3 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + L106 = A101 + A102 + A103 + A104 + A101 + A102 + A103 + AG3 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + L107 = A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A108 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A109 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A107 + L108 = A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A109 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A107 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A108 + L109 = A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A107 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A108 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A105 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A106 + A101 + A102 + A103 + A104 + A101 + A102 + A103 + A109 ______________________________________
Thus the latency of the various devices is dependent on the maximum access time of the devices. Therefore, most systems dictate maximum acess times for the devices to control the maximum latency. However, some devices require higher access time or a greater number of accesses to shared device 120 than can be allotted while satisfying the maximum latency requirements of the other devices.
FIG. 2(b) conceptually illustrates a method to increase access to shared device 120 for device 102. In FIG. 2(b), group 3 of FIG. 2(a) is modified to also include device 102. Thus device 102 can be granted access to shared device 120 based on precedence in group 0 or precedence in group 3. However, by adding device 102 into group 3, the maximum latency of accessing shared device 120 for device 107, device, 108 and device 109 is increased by approximately 33%. Furthermore, since group 3 devices are so rarely granted access to shared device 120, device 102's access to shared device 120 does not increase by a significant amount.
To provide greater access for device 102, device 102 can be placed in either group 2, group 1, or again in group 0. However, the maximum latency of accessing shared device 120 will be significantly increased for the other devices. For example if device 102 is added to group 2, the maximum latency of accessing shared device 120 for group 2 devices is increased approximately 33%. In addition the maximum latency of accessing shared device 120 for group 3 devices is also increased by 33%. Hence there is a need for a method or apparatus to arbitrate access to a shared device between a plurality of devices that can satisfy both the maximum latency requirements of various devices and the minimum access requirements of the devices.